//
//  btree.cpp
//  CppDemo
//
//  Created by 蒋益杰 on 2017/5/21.
//  Copyright © 2017年 com.ed. All rights reserved.
//

#include "btree.hpp"
#include <stack>

using namespace std;

BiTree::BiTree() {
    root = nullptr;
}

void BiTree::insert(int x) {
    insert(root, x);
}

void BiTree::remove(const int x) {
    remove(root, x);
}

bool BiTree::search(int x) {
    return search(root, x);
}

void BiTree::display() {
    display(root);
    cout << endl;
}

#pragma mark - private member
void BiTree::insert(TreeNode *&root, int x) {
    if (!root) {
        root = new TreeNode(x);
        if (!root) {
            cerr << "out of memory" << endl;
            exit(1);
        }
    } else {
        TreeNode *newNode = new TreeNode(x);
        if (!newNode) {
            cerr << "out of memory" << endl;
            exit(1);
        }
        
        TreeNode *p = root;
        while (p) {
            if (p->val > x) {
                //插入到左子树
                if (p->left) {
                    p = p->left;
                } else {
                    p->left = newNode;
                    return;
                }
            } else {
                //右
                if (p->right) {
                    p = p->right;
                } else {
                    p->right = newNode;
                    return;
                }
            }
        }
    }
}

bool BiTree::search(TreeNode *&root, const int x) {
    if (!root) {
        return false;
    }
    
    TreeNode *p = root;
    while (p) {
        if (p->val < x) {
            p = p->right;
        } else if (p->val > x) {
            p = p->left;
        } else {
            return true;
        }
    }
    return false;
}

void BiTree::remove(TreeNode *&root, const int x) {
    TreeNode *p = root;
    TreeNode *parent = nullptr;
    
    while (p) {
        if (p->val < x) {
            parent = p;
            p = p->right;
        } else if (p->val > x) {
            parent = p;
            p = p->left;
        } else {
            //找到了，开始删除
            //1 - 叶子节点
            if (!p->left && !p->right) {
                if (parent == nullptr) {
                    delete p;
                    p = nullptr;
                    root = nullptr;
                    return;
                } else {
                    parent->left == p ? parent->left = nullptr : parent->right = nullptr;
                    delete p;
                    p = nullptr;
                    return;
                }
            } else if (!p->left && p->right) { //右子树不为空
                if (parent == nullptr) {
                    root = p->right;
                    delete p;
                    p = nullptr;
                    return;
                } else {
                    parent->left == p ? parent->left = p->right : parent->right = p->right;
                    delete p;
                    p = nullptr;
                    return;
                }
            } else if (p->left && !p->right) { //左子树不为空
                if (parent == nullptr) {
                    root = p->left;
                    delete p;
                    p = nullptr;
                    return;
                } else {
                    parent->left == p ? parent->left = p->left : parent->right = p->left;
                    delete p;
                    p = nullptr;
                    return;
                }
            } else { //左右子树均不为空
                TreeNode *q = p->left;
                while (q->right != nullptr) {
                    parent = q;
                    q = q->right;
                }
                p->val = q->val;
                parent->right = p->left;
                delete q;
                q = nullptr;
                return;
            }
        }
    }
}

#pragma mark - traverse
void BiTree::preorder() {
    if (!root) {
        return;
    }
    stack<TreeNode *> stk;
    TreeNode *p = root;
    
    while (!stk.empty() || p) {
        while (p) {
            cout << p->val << ", ";
            stk.push(p);
            p = p->left;
        }
        
        if (!stk.empty()) {
            p = stk.top();
            stk.pop();
            p = p->right;
        }
    }
    cout << endl;
}

void BiTree::inorder() {
    if (!root) {
        return;
    }
    stack<TreeNode *> stk;
    TreeNode *p = root;
    
    while (!stk.empty() || p) {
        while (p) {
            stk.push(p);
            p = p->left;
        }
        
        if (!stk.empty()) {
            p = stk.top();
            stk.pop();
            cout << p->val << ", ";
            p = p->right;
        }
    }
    cout << endl;
}

void BiTree::postorder() {
    
}


void BiTree::display(TreeNode *&root) {
    //中序遍历
    inorder();
}
